package com.chenyi.data.structure.linked;

/**
 * @author by chenyi
 * @className LinkedList
 * @date 2021/12/22 12:30
 */

public class LinkedList {

    /**
     * 头节点
     */
    private Node first;

    /**
     * 尾节点
     */
    private Node last;

    /**
     * 有效个数
     */
    private int size = 0;

    /**
     * 添加
     *
     * @param e
     * @return
     */
    public boolean add(int e) {
        // 判断段是否有元素
        if (first == null) {
            first = new Node(null, e, null);
            last = first;
        } else {
            // 取出上一个节点的尾节点
            Node l = last;
            l.next = new Node(l, e, null);
            last = l.next;
        }
        size++;
        return true;
    }

    /**
     * 根据index指定插入
     *
     * @param e
     * @param index
     * @return
     */
    public boolean add(int e, int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index > (size - 1) / 2) {
            linkedLast(e, index);
        } else {
            linkedBefore(e, index);
        }
        size++;
        return true;
    }

    /**
     * 修改
     * @param e
     * @param index
     * @return
     */
    public boolean update(int e, int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node node = getNode(index);
        node.element = e;
        return true;
    }

    /**
     * 删除
     * @param index
     * @return
     */
    public boolean remove(int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node node = getNode(index);
        // 判断是否为头节点
        if (node.prev == null) {
            first = node.next;
            node.next.prev = null;
        }
        // 判断是否为为尾节点
        if (node.next == null) {
            last = node.prev;
            node.prev.next = null;
        }
        if (node.next != null && node.prev != null) {
            Node prev = node.prev;
            Node next = node.next;
            prev.next = next;
            next.prev = prev;
        }
        node = null;
        size--;
        return true;
    }

    /**
     * 根据index获取node
     * @param index
     * @return
     */
    private Node getNode(int index) {
        Node node;
        if (index > (size - 1) / 2) {
            node = queryLast(index);
        } else {
            node = queryHead(index);
        }
        return node;
    }

    /**
     * 从尾部添加
     * @param e
     * @param index
     */
    private void linkedLast(int e, int index) {
        Node node = last;
        // 判断是否要添加到最后一位
        if (index == size - 1) {
            last = new Node(node, e, null);
            node.next = last;
            return;
        }
        node = queryLast(index);
        Node prev = node.prev;
        prev.next = new Node(prev, e, node);
        node.prev = prev.next;
    }

    /**
     * 从头部添加
     * @param e
     * @param index
     */
    private void linkedBefore(int e, int index) {
        Node node = first;

        // 判断是否要添加到第一位
        if (index == 0) {
            first = new Node(null, e, node);
            node.prev = first;
            return;
        }
        node = queryHead(index);
        Node prev = node.prev;
        prev.next = new Node(prev, e, node);
        node.prev = prev.next;
    }

    /**
     * 从尾部查询
     * @param index
     * @return
     */
    private Node queryLast(int index) {
        Node node = last;
        for (int i = size - 1; i > index; i--) {
            node = node.prev;
        }
        return node;
    }

    /**
     * 从头部查询
     * @param index
     * @return
     */
    private Node queryHead(int index) {
        Node node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    /**
     * 判断index是否越界
     * @param index
     * @return
     */
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    /**
     * 输出链表
     */
    public void showLinked() {
        Node f = first;
        while (f != null) {
            System.out.println(f);
            f = f.next;
        }
    }


    public int getSize() {
        return size;
    }

    private static class Node {
        private Node prev;
        private int element;
        private Node next;

        public Node(Node prev, int element, Node next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "element=" + element +
                    '}';
        }
    }
}
